// 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，
// 其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。
// 注意：不能使用除法。
// 例如输入：[1,2,3,4,5]
// 得到输出：[120,60,40,30,24]

function constructArr(a: number[]): number[] {
    const left = new Array(a.length).fill(1);// 初始化左右积数组
    const right = new Array(a.length).fill(1);
    // 计算左前缀积
    for (let i = 1; i < a.length; i++) {
        left[i] = left[i - 1] * a[i - 1];
    }
    // 计算右后缀积
    for (let i = a.length - 2; i >= 0; i--) {
        right[i] = right[i + 1] * a[i + 1];
    }
    const b = left;// 结果数组直接赋值给其中一数组引用，节省空间
    // 任意位置的元素等于其左边前缀积乘其右边的后缀积
    for (let i = 0; i < a.length; i++) {
        b[i] = left[i] * right[i];
    }
    return b;
};

// 这道题目的难点在于不能使用除法
// 属于比较典型的利用前缀和求解的题目，比较建议用画二维表格的方式来帮助思考
// 核心的求解点在于结果数组中的任意位置的元素等于其左边所有元素的乘积乘其右边所有元素的乘积
// 我们可以使用前缀积数组的思路来求解，声明两个左右的前缀积数组
// 我们用第一轮的循环构建左边的乘积并保存在左前缀积数组中
// 第二轮的循环构建右边的乘积数组并保存在右后缀积数组中
// 最后一轮的循环直接让对应索引位置的左前缀积数组乘右后缀积数组即可得到最终的一个结果。